package leet151reversewordsinstring

// 思路一：
// 1. 先将字符串整体反转
// 2. 再将每个单词反转
// 3. 最后去掉多余的空格
// 4. 注意：提供一个辅助函数，用于反转字符串，入参为字符切片、起始位置、结束位置，原地反转即可
// 5. 时间复杂度O(n)，空间复杂度O(1)
// 6. 注意：如果字符串为空，返回空字符串
// 7. 注意：如果字符串中只有一个单词，返回该单词
// 8. 注意：如果字符串中只有一个空格，返回空字符串
// 9. 注意：如果字符串中有多个空格，返回一个空格
// 10. 注意：如果字符串中有多个单词，返回单词之间用一个空格隔开
// 11. 注意：如果字符串中有多个单词，返回单词之间用一个空格隔开，且首尾没有空格
func ReverseWords(s string) string {
	// 将字符串转换为字符切片-这一步很重要，方便反转。而且在golang中，字符串是不可变的，所以需要转换为字符切片，而且golang中字符串转切片的代价很低。
	bs := []byte(s)
	// 反转整个字符串
	reverseByteSlice(bs, 0, len(bs)-1)
	// 反转每个单词
	start := 0
	for i := 0; i < len(bs); i++ {
		if bs[i] == ' ' {
			reverseByteSlice(bs, start, i-1)
			start = i + 1
		}
	}
	// 反转最后一个单词
	if start < len(bs) {
		reverseByteSlice(bs, start, len(bs)-1)
	}
	// 去掉多余的空格
	// 使用双指针的方法原地去掉多余的空格，而不开辟新的内存空间
	// 慢指针，始终指向去掉额外多余的空格后的字符串的最后一个字符，注意连续空格缩编为一个空格
	slow := 0
	// 快指针，遍历字符串
	fast := 0
	for fast < len(bs) {
		// 跳过空格，那些需要分隔单词的空格，我们手动添加
		if bs[fast] != ' ' {
			// 在该判断范围内，我们吸收空格知道fast指向了一个空格，这样我们就完整的记录了一个单词。
			// 在该过程中同时移动slow和fast即可。
			// 如果此时slow不是0，说明我们正在添加一个新的单词，所以我们要用空格分隔开。
			if slow != 0 {
				bs[slow] = ' '
				slow++
			}
			// 这里我们就可以将fast指向的字符添加到slow指向的位置了。
			for fast < len(bs) && bs[fast] != ' ' {
				bs[slow] = bs[fast]
				slow++
				fast++
			}
		}
		fast++
	}
	// 处理末尾多余的空格
	bs = bs[:slow]
	return string(bs)
}

// 反转字符串的辅助函数
func reverseByteSlice(s []byte, start, end int) {
	// 将这个字符切片反转
	for i, j := start, end; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

// 辅助函数：去掉多余的空格
func removeExtraSpaces(s []byte) {

}
